class SegmentTree:
    def __init__(self, elements):
        self.size = len(elements)
        n = self.tableSize(self.size) + 1
        self.n = n
        self.tree = [[0, 0]] * (n * 2)
        self.lazy = [0] * (n * 2)
        for i, e in enumerate(elements):
            self.tree[i + n] = [e, 1]
        i = n - 1
        while i > 0:
            self.tree[i] = [self.tree[i*2][0] + self.tree[i*2+1]
                            [0], self.tree[i*2][1] + self.tree[i*2+1][1]]
            i -= 1
        print(self.tree)
        print(self.size)
        print(self.n)

    def tableSize(self, n):
        a = n
        a |= a >> 1
        a |= a >> 2
        a |= a >> 4
        a |= a >> 8
        a |= a >> 16
        return a

    # 把区间 [i, j) 范围内的所有值都 merge e
    def mergeRange(self, i, j, e):
        self._mergeRange(1, 0, self.n, i, j, e)

    def _mergeRange(self, pos, left, right, i, j, e):
        if right <= i or j <= left:
            return  # 啥也不做
        if i <= left and right <= j:
            self.lazy[pos] += e
            # 往上更新和
            aug = self.tree[pos][1] * e
            i = pos // 2
            while i > 0:
                self.tree[i][0] += aug
                i //= 2
            return
        mid = (left + right) // 2
        self._mergeRange(pos*2, left, mid, i, j, e)
        self._mergeRange(pos*2+1, mid, right, i, j, e)

    def merge(self, i, e):
        self._mergeRange(1, 0, self.n, i, i+1, e)

    # 注意，按照不成文的约定，包含 i 但不包含 j
    def query(self, i, j):
        return self._query(1, 0, self.n, i, j)

    def _query(self, pos, left, right, i, j):
        if right <= i or j <= left:
            return 0
        if i <= left and right <= j:
            # 往上更新和
            self._pushDown(pos)
            return self.tree[pos][0]
        self._pushDown(pos)
        mid = (left + right) // 2
        return self._query(pos*2, left, mid, i, j) + self._query(pos*2+1, mid, right, i, j)

    # 向下把 lazy 传递一层。注意，这里的 i 是 tree 中的索引
    def _pushDown(self, i):
        clazy = self.lazy[i]
        if clazy <= 0:
            return
        if i > self.n:
            self.tree[i][0] += clazy
        else:
            self.tree[i][0] += (clazy * (self.tree[i][1]))
            self.lazy[i*2] += clazy
            self.lazy[i*2+1] += clazy
        self.lazy[i] = 0


# st = SegmentTree([0, 1, 2, 3, 4, 5, 6])
# print(st.query(0, 7) == 21)
# print(st.query(0, 6) == 15)
# print(st.query(0, 5) == 10)
# print(st.query(0, 4) == 6)
# print(st.query(0, 3) == 3)
# print(st.query(0, 2) == 1)
# print(st.query(0, 1) == 0)
# print(st.query(1, 2) == 1)
# print(st.query(2, 3) == 2)
# print(st.query(3, 4) == 3)
# print(st.query(4, 5) == 4)
# print(st.query(5, 6) == 5)
# print(st.query(6, 7) == 6)
# print(st.tree)
# st.merge(3, 7)
# print(st.tree)
# print(st.lazy)
# print(st.query(0, 7) == 28)
# print(st.query(0, 6) == 22)
# print(st.query(0, 5) == 17)
# print(st.query(0, 4) == 13)
# print(st.query(0, 3) == 3)
# print(st.query(0, 2) == 1)
# print(st.query(0, 1) == 0)

# st = SegmentTree([0, 0, 0, 0, 0, 0])
# st.merge(0, 500)
# st.mergeRange(1, 4, 50)
# print(st.query(0, 6) == 650)

# st = SegmentTree([0, 1, 2, 3, 4, 5, 6])
# st.mergeRange(2, 5, 3)
# print(st.tree)
# print(st.lazy)
# print(st.query(0, 7) == 30)
# print(st.query(0, 6) == 24)
# print(st.query(0, 5) == 19)
# print(st.query(0, 4) == 12)
# print(st.tree)
# print(st.lazy)
# print(st.query(0, 3) == 6)
# print(st.tree)
# print(st.lazy)
# print(st.query(0, 2) == 1)
# print(st.tree)
# print(st.lazy)
# print(st.query(0, 1) == 0)
# print(st.query(1, 2) == 1)
# print(st.query(2, 3) == 5)
# print(st.query(3, 4) == 6)
# print(st.query(4, 5) == 7)
# print(st.query(5, 6) == 5)
# print(st.query(6, 7) == 6)
# print(st.tree)
# print(st.lazy)
# print(st.query(3, 7) == 24, st.query(3, 7))
# print(st.query(3, 5) == 13, st.query(3, 5))
# print(st.query(1, 7) == 30, st.query(1, 7))
# print(st.query(0, 7) == 30, st.query(0, 7))
# # print(st.query(2, 5) == 18, st.query(2, 5))
# print(st.query(2, 6) == 23, st.query(2, 6))
# print(st.query(2, 7) == 29, st.query(2, 7))

st = SegmentTree([0, 1, 2, 3, 4, 5, 6])
print(st.query(0, 7) == 21, st.query(0, 7))
st.mergeRange(0, 7, 1)
print(st.query(0, 7) == 28, st.query(0, 7))

[0, 30, 12, 18, 1, 14, 12, 6, 0, 1, 2, 3, 4, 5, 6, 0]
[0, 0,   0,  0, 0,  0,  0, 0, 0, 0, 3, 3, 3, 0, 0, 0]
